package com.cuz.hot100;

import com.cuz.hot100.datastruck.ListNode;

public class Q23MergeKAscendingLinkedLists {
    public static void main(String[] args) {
        //[[1,4,5],[1,3,4],[2,6]]
        ListNode l1 = ListNode.creatBy(1, 4, 5);
        ListNode l2 = ListNode.creatBy(1, 3, 4);
        ListNode l3 = ListNode.creatBy(2, 6);
        //[[],[]]
        ListNode listNode1 = ListNode.creatBy();
        ListNode listNode2 = ListNode.creatBy();
        ListNode listNode = mergeKLists1(new ListNode[]{listNode1, listNode2});
        listNode.print();
    }

    public static ListNode mergeKLists1(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        return merge(lists, 0, lists.length - 1);
    }

    private static ListNode merge(ListNode[] lists, int start, int end) {
        if (start == end) {
            return lists[start];
        }
        if (end - start != 1) {
            // 0  1   2  2/2=1 0 1 mid+1 right
            //0 1 2 3   3/2 =1  0 1 2 3
            int mid = (end + start) / 2;
            ListNode leftRes = merge(lists, start, mid);
            ListNode rightRes = merge(lists, mid + 1, end);
            return merge(new ListNode[]{leftRes, rightRes}, 0, 1);
        } else {
            ListNode list1 = lists[start];
            ListNode list2 = lists[end];
            if (list1 == null) {
                return list2;
            }
            if (list2 == null) {
                return list1;
            }

            ListNode preHead = new ListNode();
            if (list1.val <= list2.val) {
                preHead.next = list1;
                list1 = list1.next;
            } else {
                preHead.next = list2;
                list2 = list2.next;
            }
            ListNode pre = preHead.next;
            while (list1 != null && list2 != null) {
                if (list1.val <= list2.val) {
                    ListNode temp = list1.next;
                    pre.next = list1;
                    list1.next = null;
                    list1 = temp;
                } else {
                    ListNode temp = list2.next;
                    pre.next = list2;
                    list2.next = null;
                    list2 = temp;
                }
                pre = pre.next;
            }
            if (list1 == null) {
                pre.next = list2;
            }
            if (list2 == null) {
                pre.next = list1;
            }
            return preHead.next;
        }
    }
}
